package com.rui.study.algorithm.P_不同的二叉搜索树Ⅱ;

import com.rui.study.algorithm.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-15 09:20
 **/
public class Solution1_未完成 {

    /**
     * ###思路###
     *
     * @param n
     * @return
     */
    public List<TreeNode> generateTrees(int n) {
        result = new ArrayList<>();
        int[] tree = new int[(int)Math.pow(2, n)-1];
        buildTree(1, n, 0, n, tree);
        return result;
    }


    private List<TreeNode> result;
    private void buildTree(int start, int end, int index, int n, int[] tree) {
        if (start > end) {
            if (n == 0) {
                TreeNode root = new TreeNode(tree[0]);
                buildTree(tree, 0, root);
                result.add(root);
            }
            return;
        }

        // 构建二叉搜索树
        for (int i = start; i <= end; i++) {
            tree[index] = i;
            buildTree(start, i-1, 2*index + 1, n-1, tree);
            buildTree(i+1, end, 2*index + 2, n-1, tree);
            tree[index] = 0;
        }
    }

    private void buildTree(int[] tree, int target, TreeNode node) {
        int nextTarget = 2*target+1;
        if (nextTarget >= tree.length) {
            return;
        }

        int leftVal = tree[nextTarget];
        if (leftVal != 0) {
            TreeNode left = new TreeNode(leftVal);
            node.left = left;
            buildTree(tree, nextTarget, left);
        }
        nextTarget = 2*target+2;
        int rightVal = tree[nextTarget];
        if (rightVal != 0) {
            TreeNode right = new TreeNode(rightVal);
            node.right = right;
            buildTree(tree, nextTarget, right);
        }
    }


    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        Solution1_未完成 solution未完成 = new Solution1_未完成();
        List<TreeNode> result = solution未完成.generateTrees(3);
        long end = System.currentTimeMillis();
        System.out.println("不同的二叉搜索树Ⅱ：" + result.size() + ", 耗时：[" + (end - begin) + "ms]");
    }

}
